#include <iostream>
using namespace std;

template<class T>
struct Node {
    Node* left;
    Node* right;
    int deep;
    T value;

    Node(const T& val) : left(nullptr), right(nullptr), deep(-1), value(val) { }; 
};

template<class T>
class avlTree {
private:
     Node<T>* root;

    //获取节点高度
    int height(Node<T>* node) const {
        return node ? node->deep : 0;
    }

    // 右旋操作
    Node<T>* rightRotate(Node<T>* y) {
        Node<T>* x = y->left;
        Node<T>* T2 = x->right;

        x->right = y;
        y->left = T2;

        y->deep = max(height(y->left), height(y->right)) + 1;
        x->deep = max(height(x->left), height(x->right)) + 1;

        return x;
    }

    // 左旋操作
    Node<T>* leftRotate(Node<T>* x) {
        Node<T>* y = x->right;
        Node<T>* T2 = y->left;

        y->left = x;
        x->right = T2;

        x->deep = max(height(x->left), height(x->right)) + 1;
        y->deep = max(height(y->left), height(y->right)) + 1;

        return y;
    }

    //平衡因子
    int getBalance(Node<T>* root) const {
        return root ? height(root->left) - height(root->right) : 0;
    }

    // 插入操作
    Node<T>* insert(Node<T>* node, const T& value) {
        if (!node) return new Node<T>(value);

        if (value < node->value)
            node->left = insert(node->left, value);
        else if (value > node->value)
            node->right = insert(node->right, value);
        else
            return node;

        node->deep = 1 + max(height(node->left), height(node->right));

        int balance = getBalance(node);

        // 左左情况
        if (balance > 1 && value < node->left->value)
            return rightRotate(node);

        // 右右情况
        if (balance < -1 && value > node->right->value)
            return leftRotate(node);

        // 左右情况
        if (balance > 1 && value > node->left->value) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // 右左情况
        if (balance < -1 && value < node->right->value) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    //销毁树
    void destroyTree(Node<T>* node) {
        if (node != nullptr) {
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    }

    // 中序遍历
    void inorder(Node<T>* node) const {
        if (node != nullptr) {
            inorder(node->left);
            cout << node->value << " ";
            inorder(node->right);
        }
    }

    // 前序遍历
    void preorder(Node<T>* node) const {
        if (node != nullptr) {
            cout << node->value << " ";
            preorder(node->left);
            preorder(node->right);
        }
    }

    // 后序遍历
    void postorder(Node<T>* node) const {
        if (node != nullptr) {
            postorder(node->left);
            postorder(node->right);
            cout << node->value << " ";
        }
    }

    // 查找节点
    Node<T>* find(Node<T>* node, const T& value) const {
        if (node == nullptr || node->value == value)
            return node;

        if (value < node->value)
            return find(node->left, value);
        else
            return find(node->right, value);
    }

    // 查找最小节点
    Node<T>* minValueNode(Node<T>* node) {
        Node<T>* current = node;
        while (current->left != nullptr)
            current = current->left;
        return current;
    }

    // 删除操作
    Node<T>* deleteNode(Node<T>* root, const T& value) {
        if (root == nullptr) return root;

        if (value < root->value)
            root->left = deleteNode(root->left, value);
        else if (value > root->value)
            root->right = deleteNode(root->right, value);
        else {
            if ((root->left == nullptr) || (root->right == nullptr)) {
                Node<T>* temp = root->left ? root->left : root->right;
                if (temp == nullptr) {
                    temp = root;
                    root = nullptr;
                } else
                    *root = *temp;
                delete temp;
            } else {
                Node<T>* temp = minValueNode(root->right);
                root->value = temp->value;
                root->right = deleteNode(root->right, temp->value);
            }
        }

        if (root == nullptr) return root;

        root->deep = 1 + max(height(root->left), height(root->right));

        int balance = getBalance(root);

        // 左左情况
        if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);

        // 右右情况
        if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);

        // 左右情况
        if (balance > 1 && getBalance(root->left) < 0) {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }

        // 右左情况
        if (balance < -1 && getBalance(root->right) > 0) {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }

        return root;
    }
public:
    void insert(const T& value) {
        root = insert(root, value);
    }

    avlTree() : root(nullptr) {};

    explicit avlTree(const T& value) : root(new Node<T>(value)) {};

    ~avlTree() {        
        destroyTree(root);
    }

    bool find(const T& value) const {
        return find(root, value) != nullptr;
    }

    void inorderTraversal() const {
        inorder(root);
        cout << endl;
    }

    void preorderTraversal() const {
        preorder(root);
        cout << endl;
    }

    void postorderTraversal() const {
        postorder(root);
        cout << endl;
    }

    int height() const {
        return height(root);
    }

    void deleteValue(const T& value) {
        root = deleteNode(root, value);
    }
};

int main() {
    avlTree<int> avl;

    // 测试插入操作
    cout << "测试插入" << endl;
    avl.insert(10);
    avl.insert(20);
    avl.insert(5);
    avl.insert(15);
    avl.insert(25);
    avl.insert(3);
    avl.insert(7);
    avl.insert(17);

    cout << "中序遍历: ";
    avl.inorderTraversal();

    cout << "树高度: " << avl.height() << endl;

    // 测试查找操作
    cout << "\n测试查找" << endl;
    cout << "查找 15: " << (avl.find(15) ? "存在" : "不存在") << endl;  // 应存在
    cout << "查找 99: " << (avl.find(99) ? "存在" : "不存在") << endl;  // 应不存在

    cout << "\n测试删除操作" << endl;
    avl.deleteValue(25);
    cout << "删除25后中序遍历: ";
    avl.inorderTraversal();

    avl.deleteValue(5);
    cout << "删除5后中序遍历: ";
    avl.inorderTraversal();

    avl.deleteValue(20);
    cout << "删除20后中序遍历: ";
    avl.inorderTraversal();

    avl.deleteValue(10);
    cout << "删除根节点10后中序遍历: ";
    avl.inorderTraversal();

    cout << "删除后树高度: " << avl.height() << endl;

    // 测试连续插入验证平衡
    cout << "\n测试平衡" << endl;
    avlTree<int> avl_balance;
    avl_balance.insert(1);
    avl_balance.insert(2);
    avl_balance.insert(3);
    cout << "插入 1→2→3 后前序遍历: ";
    avl_balance.preorderTraversal();

    avl_balance.insert(4);
    avl_balance.insert(5);
    avl_balance.insert(6);
    cout << "插入 4→5→6 后前序遍历: ";
    avl_balance.preorderTraversal();

    return 0;
}